Message authentication is a cryptographic protocol that is useful in a variety of computer applications. There are many known techniques by which a party can authenticate a message to be sent to another party. The parties who want to authenticate messages share a secret key. An adversary should be unable (with significant probability) to produce any properly-authenticated message for any message which he or she has not yet seen. Typically, a party authenticates a message by appending to it a short string, the "message authentication code". The receiving party then applies a verification procedure on the received message and its message authentication code to decide if the transmitted message is authentic. This may be accomplished by having the receiving party compute his or her own message authentication code and check to see whether the received and generated codes match.
One prior message authentication technique with certain advantages was described by M. Wegman and L. Carter in an article titled "New hash functions and their use in authentication and set equality", J. of Computer and System Sciences, 22, 265-279 (1981). In the Wegman-Carter approach, the communicating parties S and V share a secret key "a" which is thought of as specifying a random pad "p" and a hash function "h" drawn randomly from a family of hash functions "H" having certain properties. To authenticate a message "x", the sender transmits h(x) XORed with the next piece of the pad p. Therefore, in this approach, the message x is transformed first by a non-cryptographic operation (i.e., universal hashing); only then is it subjected to a cryptographic operation (i.e., encryption).
It is desirable to be able to compute message authentication codes frequently and over message strings that are hundreds or thousands of bytes long. Typically, however, no special-purpose hardware is available for this purpose, and prior code generation and verification schemes that are software-based do not provide sufficient speed, especially when implemented on a conventional workstation or personal computer. Message authentication thus often significantly reduces the machine's overall performance.
It would therefore be desirable to provide message authentication schemes that overcome these and other disadvantages of the prior art.